package com.example.algorithm.sort;

// 学习顺序：第六
// 注意结合静图、动图来理解，光看代码理解，一开始可能会看不明白。

// 先来讲讲树形排序：
// 是一种按锦标赛的思想进行排序的方法。
// 基本思想与体育比赛时的淘汰赛类似。首先将n个对象的排序码进行两两比较，得到n/2个比较的优胜者，作为第一步比较的结果保留下来；
// 然后对这n/2个对象再进行排序码的两两比较，…，如此重复，直到选出一个排序码最小的对象为止。
// 类似于一颗二叉树，只需要把每次比较出的最小值的结点重新设置为∞，再比较出新一轮的最小值出来。复杂度：n*logn
// 这个树形排序我没有看太懂，后续了整一个代码案例，看看啥是数码排序。

// 再来说说堆排序：
// 对树形排序的进一步改进，使用一个大根堆（或者小跟堆）进行排序。堆排序的两个问题：
// 1.如何由一个无序序列“建初堆”。
// 2.输出堆顶后，如何“筛选”。筛选指对一颗子树均为堆的完全二叉树，调整根节点，使整个二叉树也成为一个堆。循环输出堆顶。

// java自带的堆排序：
// java默认是升序，也就是小根堆
// PriorityQueue<Integer> queue1 = new PriorityQueue<Integer>();
// 要使用大根堆，则需要重新实现比较器
// PriorityQueue<Integer> queue2 = new PriorityQueue<Integer>((o1,o2) -> o2 - o1);

// 构建堆
// 首先先把任意的一个数组，按照从左到右的顺序按照堆的方式排列好。
// 然后，从最后一个非叶子节点，从右边往左，从下往上，然后依次以这些节点为父节点，然后比较它与它们一个或者两个子节点之间的大小关系，该换位置的换位置。不需要换的就不换。
// 当当前节点，它的下方有两层或者两层以上的节点的时候，那么，除了比较自己这个层级以外，还要不断向下比较它下方的层级。
// 当这个过程一直进行到堆顶那个节点的时候，那么，真个数组，就调整完了。此时，它已经是一个符合堆的性质的数组了。

// 堆排序的过程
// 上面按个步骤只是让我们得到了一个真正的堆。但是，堆此时对应的数组，不一定是有序的。所以，下面，我们还要对堆进行堆排序。
// 堆排序，它会涉及一个无序区和有序区的概念。堆顶是最大的元素，堆顶元素是最值。我们首先将堆顶的元素，同时也是整个数组的排在第一位置的元素。堆的最后一个元素呢，它是最下边、最右边的元素，在数组中，它也是最排在最后的元素。
// 我们将第一个元素和最后一个元素交换位置，那么，从最后开始的那部分地方，我们就当做有序区，来存已经排好序的元素。然后剩下的其他无序区的元素，我们再给它调用一次堆化方法，让它重新符合堆的性质。重新堆化之后呢，堆顶的元素又是最值了，然后再将它和无序区的最后一个元素交换。
// 有一点可能起初会觉得有一点疑惑就是，有序区的元素，是已经排好序的元素，它是不需要参加队化的调整的。那么，在程序中我们是具体如何来区分有序区和无序区的呢？
// 其实这个比我原先想的简单，堆这个东西，其实，它在程序中，自始至终都是表现为一个数组的，在数组中区分有序区和无序区特别简单。最开始是倒数第一个是有序区、然后是倒数第一第二个、然后是倒数第一第二第三个......所以，其实蛮好表示的。直接i--就好，传给heapify(array, i, 0)方法的参数中，第二个参数表示需要做堆化的数组的长度。

//其他参考文章
// https://www.cnblogs.com/onepixel/p/7674659.html 这篇文章中的动图来理解。

// 手动实现堆排序
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 9, 8, 4, 2, 6, 1, 7};

        System.out.println("排序前的数组：");
        printArray(array);

        heapSort(array);

        System.out.println("\n排序后的数组：");
        printArray(array);
    }

    // 堆排序方法
    public static void heapSort(int[] array) {
        int n = array.length; // n = 9

        // 构建最大堆。
        // 注意，下面这个for呢，仅仅是把数组整理成符合堆的性质的。
        // 因为{5, 3, 9, 8, 4, 2, 6, 1, 7}这个数组，它不一定是满足堆属性的数组，所以，要把它先构造成满足堆属性的数组。
        // 即使变成了满足堆属性的数组，它也不一定就是排好了序的数组。有序数组一定是堆，但是堆不一定是有序数组。、
        // i 是一个索引值，表示当前要进行堆化（heapify）的节点的索引。在这段代码中，i从 n/2-1 开始递减到0，这是因为在一个数组表示的完全二叉树中，树的叶子节点是从n/2开始的。那么，第一个非叶节点，就一定是n/2-1。
        // 而构建堆的过程是从最后一个非叶子节点开始，逐渐向上进行堆化操作，直到根节点。
        for (int i = n / 2 - 1; i >= 0; i--) { // i的初始值是3，然后会经历3、2、1、0这机制值的循环。i = 3这个初始值代表的是最后一个非叶元素的索引。
            heapify(array, n, i);  // n=9, i=3。然后它就会从这里进去递归，没有递归完之前，它都不会出来走下面的for循环的哦。
        }
        // 我实际调试试验过了，heapify(array, n, i);加工之后，array它仅仅只是一个堆数组而已，但是，它不是一个有序数组。


        // 上面都仅仅只是在整理成符合堆性质，下面就是正经的堆排序了。
        // 下面这个for呢，则是把一个堆排序成一个有序数组
        // 依次将堆顶元素与堆的最后一个元素交换位置，并重新构建堆
        for (int i = n - 1; i >= 0; i--) { // 就是简单的遍历array数组而已。是从数组后面往前遍历的。
            // 将堆顶元素（最大元素）与堆的最后一个元素交换位置
            int temp = array[0];  // array[0]是数组的第一个元素，其实对应到堆中呢，也必然是堆顶的元素。临时取出来。
            array[0] = array[i]; // array[i]按它的初始值来算的话，array[n-1]是数组的最后一个元素。同时也是堆最后一个元素。
            array[i] = temp; // 这三句相当于是array[0]与array[i]互换值。

            // 重新构建堆，为什么需要重新堆化呢，因为我们做了节点替换啊，有序区的最后一个节点和第一个节点互换。
            // 第二个参数i表示做堆化的数组的长度，下面这个方法是在交换之后首次调用的，所以，i此时已经应该用n-1了，所以，i的初始值在for循环上写的是n-1。并且随着无序区的不断缩短，i是递减的。
            // 第三个参数如何理解呢？第三个参数，表示当前需要做堆性质比较的三角形的顶点。我们也明白，那个节点自己的值动了，那么，就把这个节点的索引丢进这个heapify方法的第三个参数做堆化。因为是堆的顶点被动了，所以，就把0丢进去做堆化。并且，在排序阶段每次都是把堆顶的值动了，所以，固定就是以0节点为第三个参数做堆化。所以下面的方法可以固定写0。
            // 那可能会疑问了，做堆化不是从最后一个非叶节点开始做堆化吗。如果我们采用这种方式，就意味着我们要在下面再写一个：
            //for (int i = n / 2 - 1; i >= 0; i--) {
            //    heapify(array, n, i);
            //}
            // 上面这个，其实是包含了heapify(array, i, 0)这个逻辑的。
            // 但是，对于现在的我们来说，对于增量的变化来说，只用针对动了的那个节点为起始节点做堆化就好了，不用在从最后一个非叶节点开始做一次全量的堆化了。
            heapify(array, i, 0);  // array是原始数组。i是啥意思我没弄懂。0是一个索引，表示的是数组第一个元素。
        }
    }

    // 构建堆方法
    public static void heapify(int[] array, int n, int i) { // 首次进来，n=9，i=3
        int largest = i; // 最后一个非叶子节点的坐标。我们堆化的时候，是从它开始的。然后从右往左、从下往上遍历。同时，我们也暂时先认为这个位置的值，是当前三角形三个节点中的最大值。还没开始打擂台嘛。
        int left = 2 * i + 1; // 左子节点索引。左子节点的索引，必然满足这个公式。  第一次：left = 7
        int right = 2 * i + 2; // 右子节点索引。同上。  第一次：right = 8

        // left < n 应该是一定满足的。毕竟n就是长度。
        // 如果左子节点大于当前节点，那么，把这个节点的位置，保存在临时变量largest里面。因为表示不符合堆的性质，后续是要调整的。
        // 这里仅仅是在改变largest变量而已，擂台思想。但是对于数组本身，我们并没有动。
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        // 如果右子节点大于当前节点，那么，把这个节点的位置，保存在临时变量largest里面。
        // 这里仅仅是在改变largest变量而已，擂台思想。但是对于数组本身，我们并没有动。
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        // 把上面两个if如果都走完之后，其实就是相当于父、左子、右子这三个节点都已经比较完了，然后从中找出了值最大的节点，并且将它的索引存入了largest这个临时变量。
        // 三个元素确定最值，至少要比较两次。所以，上面是两次比较。后续交换的时候，只用交换一次，把最值交换到三角形的顶点就好(当然没有左节点或者没有右节点的，自然也会少一次比较)。


        // largest == i，那表示，i位置上的值在三角关系中，本来就是最大值，那么，它本来就符合堆性质，我们这个主节点进来堆化，左右判断都没进，节点也不需要做任何调整。
        // largest != i，那表示当前父节点所主导的三角关系，需要做节点调整。
        if (largest != i) { // 这个判断是必要的，因为呢，有可能上面两个if根本就没有进去，所以呢，largest还是的值还是i。还是i的话，那就没必要进这个if走array的实际的替换的逻辑了。
            // 下面这三句呢，就是把array[i]与array[largest]互换位置。i、largest都是索引。
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;

            // 递归构建子堆
            // 可以认为，largest就是指，要做判断的那个三角关系中父节点的索引。
            // 递归的时候，其实array, n一丁点都没有变，唯一变化的是largest这个变量的值。
            // 而这个largest的值，它是怎么确定的呢？三个节点比较，确定最大值，需要比较两次。这是常识。而三个节点中，最大的那个值，它必然大于其他任意的两个值，这也是常识。那么，比较的话，我们可以比较两次，但是，交换的话，其实一次就够了。因为我们只需要将最大的那个值交换到局部三角形的顶点就行。
            // 所以，你可以看到，虽然largest如果上面左右两个if都满足的话，可能会被重新赋值两次。但是，largest仅仅只是一个装索引的变量而已，我们最终操作array[i]和array[largest]的交换，仅仅只做了一次。
            // 所以，我们现在来从多个角度来说明下largest的值是啥。它是三个值中最大的那个值原先所在位置的索引。为什么要把largest这个值再次传入heapify方法来做递归，原因是因为，largest这个位置的值，是新交换过来的，它可能与它自己的子树已经不满足堆的性质了，虽然整个构建堆的过程我们是从下到上、从右到左，所以，当前节点的下方其实之前就已经调整过使它符合堆的性质，但是，因为上级节点调整时又会动到下级节点，所以，动了的，要重新走递归堆化的过程。
            heapify(array, n, largest);
        }
    }

    // 打印数组方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}


// 后记：
// 堆排序，和冒泡选择、插入、归并快拍这些都没太多共同点，所以，单独作为一类。这个我个人认为，也是最麻烦的。

